12.6 KB · ⇊ 4 parts · ⤓ Micron 12.6 KB · ⤓ HTML 59.3 KB

top

Die Box-Muller-Methode (nach George Edward Pelham Box und Mervin Edgar Muller 1958) ist ein Verfahren zur Erzeugung normalverteilter Zufallszahlen.

• Definition

• Programmierung

• Weblinks

• Literatur

• Einzelnachweise

Bei dieser Methode werden zunächst zwei unabhängige Standardzufallszahlen u 1 {\displaystyle u_{1}} und u 2 {\displaystyle u_{2}} benötigt. Diese lassen sich beispielsweise mit einem Zufallszahlengenerator erzeugen. Standardzufallszahlen unterliegen einer Rechteckverteilung mit den Parametern 0 {\displaystyle 0} und 1 {\displaystyle 1} .

Es lässt sich zeigen, dass man nach folgendem Transformationsschritt daraus zwei standardnormalverteilte (stochastisch) unabhängige Zufallszahlen z 0 {\displaystyle z_{0}} und z 1 {\displaystyle z_{1}} erhält:

z 0 = − − 2 ln ⁡ ⁡ u 1 cos ⁡ ⁡ ( 2 π π u 2 ) {\displaystyle z_{0}={\sqrt {-2\ln u_{1}}}\cos(2\pi u_{2})}

und

z 1 = − − 2 ln ⁡ ⁡ u 1 sin ⁡ ⁡ ( 2 π π u 2 ) {\displaystyle z_{1}={\sqrt {-2\ln u_{1}}}\sin(2\pi u_{2})} .

Schreibt man das Paar ( z 0 , z 1 ) {\displaystyle (z_{0},z_{1})} in Polarkoordinaten, also

z 0 = r cos ⁡ ⁡ φ φ {\displaystyle z_{0}=r\cos \varphi } und z 1 = r sin ⁡ ⁡ φ φ {\displaystyle z_{1}=r\sin \varphi } ,

dann gilt:

r = − − 2 ln ⁡ ⁡ u 1 {\displaystyle r={\sqrt {-2\ln u_{1}}}\ } und φ φ = 2 π π u 2 {\displaystyle \varphi =2\pi u_{2}} .

Anwendung der Inversionsmethode zur Transformation von u 1 {\displaystyle u_{1}} und u 2 {\displaystyle u_{2}} in die Polarkoordinaten r {\displaystyle r} und φ φ {\displaystyle \varphi } zeigt, dass φ φ {\displaystyle \varphi } einer Rechteckverteilung mit den Parametern 0 {\displaystyle 0} und 2 π π {\displaystyle 2\pi } unterliegt und r 2 {\displaystyle r^{2}} einer Exponentialverteilung mit dem Parameter 1 2 {\displaystyle {\tfrac {1}{2}}} . Aus diesem Ergebnis lässt sich die gemeinsame Verteilung von z 1 {\displaystyle z_{1}} und z 2 {\displaystyle z_{2}} herleiten. Sie beruht auf der Beziehung:

1 2 e − − 1 2 r 2 d ( r 2 ) 1 2 π π d φ φ = 1 2 π π e − − 1 2 r 2 r d r d φ φ = 1 2 π π e − − 1 2 ( z 0 2 + z 1 2 ) d z 0 d z 1 {\displaystyle {\tfrac {1}{2}}e^{-{\frac {1}{2}}r^{2}}\mathrm {d} (r^{2}){\tfrac {1}{2\pi }}\mathrm {d} \varphi ={\tfrac {1}{2\pi }}e^{-{\frac {1}{2}}r^{2}}r\mathrm {d} r\mathrm {d} \varphi ={\tfrac {1}{2\pi }}e^{-{\frac {1}{2}}(z_{0}^{2}+z_{1}^{2})}\mathrm {d} z_{0}\mathrm {d} z_{1}}

Die bisherigen Transformationsschritte erzeugen zwei standardnormalverteilte Zufallszahlen. Eine Standardnormalverteilung ist ein Spezialfall der Normalverteilung, nämlich mit dem Erwartungswert μ μ = 0 {\displaystyle \mu =0} und der Varianz σ σ 2 = 1 {\displaystyle \sigma ^{2}=1} .

Um mit der Box-Muller-Methode Normalverteilungen mit beliebigen Parametern zu erzeugen, lassen sich die erhaltenen z i {\displaystyle z_{i}} nach dem Muster

x i = μ μ + σ σ ⋅ ⋅ z i {\displaystyle x_{i}=\mu +\sigma \cdot z_{i}}

transformieren. In der obigen Notation steht π π {\displaystyle \pi } wie üblich für die Kreiszahl, sin {\displaystyle \sin } für den Sinus, cos {\displaystyle \cos } für den Kosinus und ln {\displaystyle \ln } für den natürlichen Logarithmus.

Verwendet man zur Erzeugung der u i {\displaystyle u_{i}} einen linearen Kongruenzgenerator, so liegen die Paare ( z 0 , z 1 ) {\displaystyle (z_{0},z_{1})} auf einer durch eine Spirale beschriebenen Kurve. Dieses Verhalten ist eng mit dem im Satz von Marsaglia beschriebenen Hyperebenenverhalten linearer Kongruenzgeneratoren verwandt.

Dieses Problem lässt sich umgehen, wenn statt des linearen Kongruenzgenerators ein inverser Kongruenzgenerator oder die Polar-Methode verwendet wird.

Die Box-Muller-Methode erzeugt zunächst zwei stochastisch unabhängige und standardnormalverteilte Zufallszahlen, die sich dann in eine Normalverteilung mit beliebigen Parametern transformieren lassen. Die Box-Muller-Methode erfordert die Auswertung von Logarithmen und trigonometrischen Funktionen, was auf einigen Rechnern sehr zeitaufwendig sein kann.

Weitere Möglichkeiten zur Erzeugung normalverteilter Zufallszahlen sind im Artikel Normalverteilung beschrieben. Eine Alternative ist z. B. die Polar-Methode.cite-ref-1[1]

Die Standard-Box-Muller-Methode erzeugt Werte aus der Standardnormalverteilung mit Erwartungswert 0 und Standardabweichung 1. Die folgende Implementierung in der Programmiersprache C++ generiert 10 Paare von standardnormalverteilten Zufallszahlen aus jeder Normalverteilung mit Erwartungswert μ μ {\displaystyle \mu } und Varianz σ σ {\displaystyle \sigma } und gibt sie auf der Konsole aus.

• Eric W. Weisstein: Box-Muller Transformation. In: MathWorld (englisch).

• George Edward Pelham Box, Mervin Edgar Muller: A note on the generation of random normal deviates. In: Annals of Mathematical Statistics, Jg. 29 (1958), Heft 2, ISSN 0003-4851, S. 610–611.

• Donald Ervin Knuth: The Art of Computer Programming, Sec. 3.4.1, S. 117.

• Otto Moeschlin, Eugen Grycko, Claudia Pohl, Frank Steinert: Kapitel 1.4 Generating Sample Values. In: Diess.: Experimental Stochastics. Springer, Berlin u. a. 1998, ISBN 3-540-14619-9.

cite-note-11. ↑ Vgl. Albert J. Kinderman und John G. Ramage: Computer Generation of Normal Random Numbers. In: Journal of the American Statistical Association, Jg. 71 (1976), Heft 356, S. 893–896.